package p03_SingleLinkedList.quiz.q06_JosephusProblem;

import org.junit.jupiter.api.Test;

/**
 * 剑指 Offer 62. 圆圈中最后剩下的数字
 * <p>
 * 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
 * <p>
 * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCodeSolution {
    //region 自己写的，有问题

    /**
     * 数组
     *
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining(int n, int m) {
        int[] arr = new int[n];
        boolean[] flags = new boolean[n];
        int counter = 0;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
            flags[i] = false;
        }
        int c = m;
        while (counter != n - 1) {
            flags[(c - 1) % n] = true;
            counter++;
            c = cpp(c, n, m, flags, 0);
        }
        c = 0;
        while (flags[c]) {
            c++;
        }
        return arr[c];
    }

    public int cpp(int c, int n, int m, boolean[] flags, int count) {
        c++;
        if (!flags[(c - 1) % n]) {
            count++;
        }
        if (flags[(c - 1) % n] || count < m) {
            c = cpp(c, n, m, flags, count);
        }
        return c;
    }
    //endregion

    @Test
    public void test01() {
        int temp = lastRemaining2(70866, 116922);
        System.out.println("===========");
        System.out.println(temp);
    }

    /**
     * 数组实现，有缺陷
     *
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining2(int n, int m) {
        int count = 0;
        int i = -1;
        int k = 0;
        boolean[] flags = new boolean[n];
        int[] res = new int[n];
        for (int j = 0; j < flags.length; j++) {
            flags[j] = false;
        }
        while (count != n) {
            i++;
            if (i >= n) {
                i = 0;
            }
            if (!flags[i]) {
                k++;
                if (k == m) {
                    flags[i] = true;
                    count++;
                    res[count - 1] = i;
//                    System.out.println(i);
                    k = 0;
                }
            }
        }
        return res[res.length - 1];
    }


    public int lastRemaining1(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = lastRemaining1(n - 1, m);
        return (m + x) % n;
    }
}
